package course.p3_arraysSort.exa04_quickSort;

import java.util.Arrays;
import java.util.Random;

public class IntQuickSort {


    /**
     * 三数中值找到key并和right位置交换
     * @param a 目标数组
     * @param left 左位置
     * @param right 右位置
     * @return
     */
    public static int median3(int[] a, int left,int right) {
        int center = (left+right)/2;
        // left为中值
        if(a[left]>=a[center]&&a[left]<=a[right]||a[left]>=a[right]&&a[left]<=a[center]){
            swap(a,left,right);
        }
        // center为中值
        else if(a[center]>=a[left]&&a[center]<=a[right]||a[center]>=a[right]&&a[center]<=a[left]) {
            swap(a,center,right);
        }
        return a[right];
    }

    /**
     * 随机选取key
     * @param a
     * @param left
     * @param right
     * @return
     */
    public static int randomKey(int[] a,int left,int right) {
        Random random = new Random();
        int index = random.nextInt(right-left+1)+left;
        swap(a,index,right);
        return a[right];
    }

    /**
     * 交换left和right位置的元素
     * @param a
     * @param left
     * @param right
     */
    public static void swap(int[]a ,int left,int right) {
        if(left<0||right<0||left>=a.length||right>=a.length){
            System.out.println("left或right位置错误！！");
        }
        int tem = a[left];
        a[left] = a[right];
        a[right] = tem;
    }

    /**
     * 2个或三个的元素就不用执行主流程了，直接进行普通的排序
     * @param a
     * @param left
     * @param right
     */
    public static void easySort(int[] a, int left, int right) {
        int center = left+1;

        if(a[left]>a[center]){
            swap(a,left,center);
        }

        if(a[left]>a[right]){
            swap(a,left,right);
        }

        if(a[center]>a[right]){
            swap(a,center,right);
        }

    }

    public static void quickSort(int[] a){
        quickMain(a,0,a.length-1);
    }

    public static void quickMain(int[] a, int left, int right) {
        if(left>=right||right<0||left>=a.length||left<0||right>=a.length) {
            return;
        }
        //如果元素超过3个，执行快排流程
        if(left+3 <= right) {
            int i ,j = right-1 ,key;
            //key = median3(a,left,right);
            key = randomKey(a,left,right);
            for(i = left;i <= j;) {
                if(a[i] <= key) {
                    i++;
                }
                if(a[j] >= key){
                    j--;
                }
                if(i<j&&a[i]>key&&a[j]<key){
                    swap(a,i,j);
                }
            }
            swap(a,i,right);
            // 此时i位置就是中间位置
            // 需要对剩下的元素进行快排操作
            quickMain(a,left,i-1);
            quickMain(a,i+1,right);
        }
        // 简单排序
        else{
            easySort(a,left,right);
        }
    }


    public static void main(String[] args) {
        int[] numbs = {5,1,1,2,0,0};
        quickSort(numbs);
        System.out.println(Arrays.toString(numbs));
    }

}
